import java.util.ArrayList;
import java.util.List;

/**
 * @作者 zxy
 * @时间 2023-04-25 13:18
 * @说明 1380. 矩阵中的幸运数
 * 给你一个 m * n 的矩阵，矩阵中的数字 各不相同 。请你按 任意 顺序返回矩阵中的所有幸运数。
 * 幸运数 是指矩阵中满足同时下列两个条件的元素：
 * 在同一行的所有元素中最小
 * 在同一列的所有元素中最大
 * 示例 1：
 * 输入：matrix = [[3,7,8],[9,11,13],[15,16,17]]
 * 输出：[15]
 * 解释：15 是唯一的幸运数，因为它是其所在行中的最小值，也是所在列中的最大值。
 */
public class Solution {
    /**
     * 执行用时：4 ms, 在所有 Java 提交中击败了11.01%的用户
     * 内存消耗：41.6 MB, 在所有 Java 提交中击败了97.36%的用户
     * @param matrix
     * @return
     */
    public List<Integer> luckyNumbers(int[][] matrix) {
        List<Integer> list = new ArrayList<>();
        int[] recMinRow = new int[10001];
        int[] maxColumn = new int[matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            int minRow = Integer.MAX_VALUE;
            for (int i1 = 0; i1 < matrix[i].length; i1++) {
                if (maxColumn[i1] < matrix[i][i1]) maxColumn[i1] = matrix[i][i1];
                if (minRow > matrix[i][i1]) minRow = matrix[i][i1];
            }
            recMinRow[minRow] = 1;
        }
        for (int i = 0; i < maxColumn.length; i++) {
            if (recMinRow[maxColumn[i]] == 1)
                list.add(maxColumn[i]);
        }
        return list;
    }
}
